package org.datastructure.secondday.sort;

import com.sun.corba.se.impl.orb.ParserTable;

import java.util.Arrays;

public class heapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort hs = new heapSort();
        hs.heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public void heapSort(int[] arr) {
        for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
            ajust(arr, i, arr.length);
        }

        for (int i = arr.length-1; i >= 0; i--) {
            int stemp = arr[0];
            arr[0] = arr[i];
            arr[i] = stemp;

            ajust(arr, 0, i);
        }
    }

    /**
     * 调整位置，该方法与插入排序类似，都是让当前节点与子节点比较，寻找插入位置
     *
     * @param arr
     * @param index
     * @param lenth
     */
    public void ajust(int[] arr, int index, int lenth) {
        // TODO: 2022/1/28 首先需要把arr[index]赋值给一个临时变量，用来存储顶节点，最后需要将他赋值给调整后的位置
        int stemp = arr[index];
        // TODO: 2022/1/28 找到当前index的左右叶子节点，并循环处理他的下级节点
        for (int i = index * 2 + 1; i < lenth; i = i * 2 + 1) {
            // TODO: 2022/1/28 找出两个叶子节点的最大值
            if (i + 1 < lenth && arr[i] < arr[i + 1]) {
                i++;//指向最大值
            }
            // TODO: 2022/1/28 如果叶子节点比父节点大，就把他赋值给父节点，且让父节点的索引指向他本身
            if (arr[i] > stemp) {
                arr[index] = arr[i];
                index = i;
            }
        }

        // TODO: 2022/1/28 再让该节点的左右叶子节点与最初的stemp与之比较，寻找stemp应该出入的位置，并交换
        arr[index] = stemp;
    }
}
